/**
 * @author LKQ
 * @date 2021/12/30 17:04
 * @description 我是废物
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] height = {4,2,0,3,2,5};
        System.out.println(solution.trap(height));
    }

    public int trap(int[] height) {
        int n = height.length, ans = 0, left = 0, right ;
        for (int i = n-2 ; i >= 0;) {
            // 找到升序的最后的一个数字
            while (i >= 0 && height[i] >= height[i+1]) {
                i--;
            }
            right = i + 1;
            // 找到左边界
            int max = height[right];
            // 如果寻找左边界时，一直都是降序，说明无法存水。
            int temp = right-1;
            while (temp >= 0 && height[temp] <= height[temp+1]) {
                temp--;
            }
            if (temp == -1) {
                break;
            }
            for (int j = right - 2; j >= 0; j--) {
                if (height[j] > max) {
                    max = height[j];
                    break;
                }
            }
            for (int  k = right - 2; k >= 0; k--) {
                if (height[k] == max) {
                    left = k;
                    break;
                }
            }
            int low = Math.min(height[left], height[right]);
            ans += (right - left + 1) * low;
            for (int j = left; j <= right; j++) {
                ans -= Math.min(height[j], low);
            }
            i = left;
            if (i == 0) {
                break;
            }
        }
        return ans;
    }
}
